1. Field of the Invention
The present invention relates to a method and system for generating an image in computer graphics, and more specifically to an image generating method and system capable of speedily executing a hidden surface removal.
2. Description of the Related Art
It is known to use a Z-buffer method as an image generating method for generating a hidden surface removed image of a three-dimensional object in computer graphics (for example, Japanese Patent Application Pre-examination Publication No. JP-A-62-222379). The Z buffer method uses a Z buffer storing a depth value of each pixel, indicative of the distance from a viewpoint to each pixel, in the amount of one frame. The Z-buffer also stores a frame buffer storing a brightness value of each pixel, indicative of the brightness of each pixel, in the amount of one frame. For each pixel, the depth value stored in the Z buffer is compared with the depth value of a newly calculated three-dimensional object. The depth value nearer to the viewpoint and the corresponding brightness value are left in the Z buffer and the frame buffer, so that a hidden surface removed image is finally generated in the frame buffer. In this method, it is necessary to read, modify and write to the frame buffer for each of pixels included in a projected image formed by projecting the three-dimensional object onto a picture plane. Therefore, in order to speedily execute the image generation, it is necessary to speedily perform a random access to a large capacity memory which constitutes the frame buffer.
A high speed memory, called SRAM (static random accesses memory) is used in a method for speedily performing a random access to the memory, in order to increase the bus band width of the memory. Alternatively, memories have been operated in a parallel.
In the above mentioned conventional image generation method, in order to speedily perform the random access to the frame buffer, an expensive memory has been used, or alternatively, in order to operate memories in parallel, it has been necessary to use a large number of memories and to increase the number of signal lines in accordance with the degree of parallelism. Therefore, there was a problem in that the apparatus became large scale and expensive.
On the other hand, a large-capacity, low-cost, high-speed-accessible memory such as a high speed DRAM (dynamic random access memory) has recently started to be manufactured. However, since there is a restriction that the random access cannot be freely performed, there occurs a problem in which the performance of the memory cannot be sufficiently utilized in the conventional Z-buffer method.
It is an object of the present invention to provide image generating method and system in computer graphics, which have overcome the above mentioned problems of the prior art.
Another object of the present invention is to provide image generating method and system capable of speedily generating an image even with a low-cost memory such as a high speed DRAM, by dividing a picture frame into a plurality of rectangular blocks (hereinafter, xe2x80x9cblockxe2x80x9d) and repeating generation of a hidden surface removed block image.
One example of a prior art using a procedure for dividing picture data into a plurality of block areas is disclosed by Japanese Patent Application Pre-examination Publication No. JP-A-01-112377 entitled xe2x80x9cPicture Information Processorxe2x80x9d. However, this apparatus is configured to encode in units of blocks, and is completely different in object and in construction from the present invention.
In an image generation method for generating a hidden surface removed image, an object located in a three-dimensional space being defined as a collection of primitives which are fundamental shapes, and a hidden surface removal being conducted on the basis of a depth value indicating a distance from a viewpoint to each of pixels in a picture frame composed of pixels arranged in the form of matrix, the method in accordance with the present invention is characterized by including dividing the picture frame into a plurality of rectangular blocks, preparing a cache memory for storing a brightness value and a depth value of each pixel, in the amount of at least one block, and repeating a processing including to segment the primitive into a collection of in-block spans which are completely included in one block, and to generate on the basis of the collection of in-block spans a hidden surface removed block image in the cache memory, whereby an image of one picture frame is generated.
Alternatively, in an image generation method for generating a hidden surface removed image, an object located in a three-dimensional space being defined as a collection of primitives which are fundamental shapes, and a hidden surface removal being conducted by using a Z buffer and a frame buffer, which correspond to position of pixels in a picture frame composed of pixels arranged in the form of matrix, and which respectively store a depth value indicating a distance from a viewpoint to each pixel and a brightness value indicating a brightness of each pixel, on the basis of the depth value, the method in accordance with the present invention is characterized by including:
a cache initializing step for initializing into an empty condition a cache memory capable of storing pixel values in the amount of at least one rectangular block of a plurality of rectangular blocks obtained when the picture frame is divided into the plurality of rectangular blocks;
a step for discriminating whether or not a primitive exists, in which if in all the primitives constituting the object there exists a primitive which has not yet been extracted, the primitive is extracted, and if there is no primitive which has not yet been extracted, the processing goes into an ending processing;
a projected block extracting step for extracting all blocks including a projected image of the primitives projected onto the picture frame;
a step for discriminating whether or not a block exists, in which if in all the blocks including the projected image of the primitives projected onto the picture frame, there exists a block which has not yet been extracted, the block is extracted, and if there is no block which has not yet been extracted, the processing returns into the step for discriminating whether or not the primitive exists;
a cache replacement step in which if the pixel values of the extracted block are not stored in the cache memory, the pixel values of the extracted block are written into the cache memory, and when the cache memory stores the pixel values of another block and therefore the pixel values of the extracted block are overwritten into the cache memory, the pixel values of the another block are written into the Z buffer and the frame buffer;
an in-block span generating step for seeking in-block span information obtained when the primitive is segmented into a collection of in-block spans so that a projected image of the primitive completely falls in the extracted block;
a block image generating step for obtaining the pixel values of the pixels included in the in-block spans from the in-block span information, comparing the depth values of the pixel values with the depth values of the extracted block stored in the cache memory, and preserving, in the cache memory, the pixel values of the in-block spans which can be viewed from the viewpoint, and then, returning to the step for discriminating whether or not the block exists; and
a cache exhausting step for writing the brightness values stored in the cache memory into the frame buffer, as the ending processing in the step for discriminating whether or not the primitive exists.
Furthermore, the image generation method in accordance with the present invention is also characterized in that, in the cache replacement step, if the pixel values of the extracted block are not stored in the cache memory, the pixel values of the extracted block are written into the cache memory, and when the cache memory stores the pixel values of another block and therefore the pixel values of the extracted block are overwritten into the cache memory, only modified pixel values of the pixel values of the another block are written into the Z buffer and the frame buffer.
Moreover, in an image generation method for generating a hidden surface removed image, an object located in a three-dimensional space being defined as a collection of primitives which are fundamental shapes, and a hidden surface removal being generated, in a frame buffer which corresponds to pixels in a picture frame composed of pixels arranged in the form of matrix and which stores a brightness value indicating a brightness of each pixel, on the basis of a depth value indicating a distance from a viewpoint of the primitive to each pixel, the method in accordance with the present invention is characterized by including:
a cache initializing step for initializing into an empty condition a cache memory capable of storing pixel values composed of the brightness values and the depth values of the pixels, in the amount of at least one rectangular block of a plurality of rectangular blocks obtained when the picture frame is divided into the plurality of rectangular blocks;
an all-primitive position calculating step for determining and storing, for all the primitives, position information indicating a block having possibility of including a projected image of each primitive;
a step for discriminating whether or not a block exists, in which if in all the blocks constituting the picture frame, there exists one or more blocks which have not yet been extracted, one block is extracted in an arrangement order on the picture frame;
a primitive extracting step for extracting, on the basis of the position information, all primitives each having possibility that a projected image of that primitive is included in the extracted block;
a step for discriminating whether or not a primitive exists, in which if in all the primitives extracted, there exists a primitive which has not yet been extracted, the primitive is extracted, and if there is no primitive which has not yet been extracted, the processing goes into an ending processing;
an in-block span generating step for seeking in-block span information obtained when the extracted primitive is segmented into a collection of in-block spans so that a projected image of the extracted primitive completely falls in the extracted block;
a block image generating step for obtaining, from the in-block span information, the pixel values of the pixels included in the in-block spans from the in-block span information, comparing the depth values of the pixel values with the depth values of the extracted block stored in the cache memory, and preserving, in the cache memory, the pixel values of the primitive which can be viewed from the viewpoint, and then, returning to the step for discriminating whether or not the primitive exists; and
a cache exhausting step for writing the brightness values stored in the cache memory into the frame buffer, and initializing the cache memory into the empty condition, as the ending processing in the step for discriminating whether or not the primitive exists, and then, for returning to the step for discriminating whether or not the block exists.
On the other hand, an image generation apparatus in accordance with the present invention is characterized by comprising:
a primitive setting section for setting primitive information indicating each of primitives when an object located in a three-dimensional space is defined as a collection of primitives which are fundamental shapes;
a memory including a Z buffer and a frame buffer, which respectively store a depth value indicating a distance from a viewpoint to each of pixels of the picture frame and a brightness value indicating a brightness of each pixel;
a cache memory capable of storing pixel values each composed of the depth value and the brightness value of each pixel, in the amount of at least one rectangular block of a plurality of rectangular blocks obtained when the picture frame is divided into the plurality of rectangular blocks;
a block segmenting section for seeking, on the basis of the primitive information, in-block span information obtained when the primitive is segmented into a collection of in-block spans so that a projected image of the primitive completely falls in one block, the block segmenting section also seeking block information indicating a block including a projected image of the primitive projected onto the picture frame;
an in-block span storing section for storing the in-block span information;
a cache controlling section operating on the basis of the block information to writing the pixel values of the block into the cache memory from the memory if the pixel values of the block are not stored in the cache memory, the cache controlling section operating, when the cache memory stores the pixel values of another block and therefore the pixel values of the block are overwritten into the cache memory, to write the pixel values of the another block into the memory, the cache controlling section reading from the in-block span storing section the in-block span information indicating the in-block span projected onto the block;
a pixel processing section for seeking from the in-block span information the pixel value of the pixel included in the in-block span, and reading out the depth value in the block stored in the cache memory by action of the cache controlling section, to compare the read-out depth value with the depth value of the pixel, and further writing the pixel values which can be viewed from the viewpoint, into in the cache memory by action of the cache controlling section; and
an image display for displaying the image stored in the frame buffer.
Furthermore, the image generation apparatus in accordance with the present invention is also characterized in that the cache controlling section has a flag indicating whether or not each block has been used, and performs such a control that for a block which has not yet been used, the pixel values are not read out from the memory to be written into the cache memory.
In addition, the image generation apparatus in accordance with the present invention is also characterized in that the cache controlling section performs such a control that when the pixel values of the another block are written into the memory, unmodified pixels values are not written into the memory.
Alternative, the image generation apparatus in accordance with the present invention is also characterized in that the cache controlling section has a flag indicating whether or not each block has been used, and performs such a control that for a block which has not yet been used, the depth values are not read out from the memory to be written into the cache memory.
Still further, an image generation apparatus in accordance with the present invention is characterized by comprising:
a primitive setting and storing section for setting and storing primitive information indicating each of primitives when an object located in a three-dimensional space is defined as a collection of primitives which are fundamental shapes,
a memory storing a brightness value indicating a brightness of the primitive in each of pixels of the picture frame;
a cache memory capable of storing pixel values each composed of a depth value indicating a distance from a viewpoint to each pixel and the brightness value of each pixel, in the amount of at least one rectangular block of a plurality of rectangular blocks obtained when the picture frame is divided into the plurality of rectangular blocks;
a block sorting section for reading, from the primitive setting. and storing section in the arrangement order of the blocks in the picture frame, the primitive information indicating the primitive having possibility that a projected image of the primitive is included in the block, the block sorting section generating an end information for notifying the ending of the block;
a block segmenting section for seeking, on the basis of the primitive information, in-block span information obtained when the primitive is segmented into a collection of in-block spans so that a projected image of the primitive completely falls in one block;
an in-block span storing section for storing the in-block span information;
a cache controlling section responding to the end information to read from the in-block span storing section the in-block span information indicating the in-block span projected onto the block, and for writing the brightness values stored in the cache memory into the frame buffer when the processing for the block is completed;
a pixel processing section for seeking from the in-block span information the pixel value of the pixel included in the in-block span, and reading out the depth value in the block stored in the cache memory by action of the cache controlling section, to compare the read-out depth value with the depth value of the pixel, and further writing the pixel values which can be viewed from the viewpoint, into in the cache memory by action of the cache controlling section; and
an image display for displaying the image stored in the frame buffer.